package SFT;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

/**SFTImplementation.java
 * This is the actual implementation of the SFT main Algorithm.
 * The algorithm receives the indices of the segment upon which the algorithm should be applied
 * (from and to), the desired tau and delta as well as the function and its supremal norm.
 * The function returns a TimeElements object contains the heavy coefficients in the segments.
 * Annotations inside the code are simply the corresponding pseudocode lines from the thesis.
 * SEE: TimeElements
 * @author Baruch Weizman, Oren Gilon, Barak Arkis
 */
public class SFTImplementation {
	/**/
	/*coefficients for mA and mB in Akavia's thesis*/
	private static final double mA_COEFF = 0.0000003;
	private static final double mB_COEFF = 0.0000003;
	
	/*just a helpful global variable*/
	static long mB;
	
	/**Algorithm 3.4 SFT*/
	public static TimeElements SFT(int from, int to, double tau, double delta, double infNorm, Function funct) {
		subSet[] list;
		List<subSet> retLst;
		Map<Integer, Complex> query;
		int sizeOfGroup=to-from+1;
		double delta_mark=(double) (delta/(Math.pow(funct.eucNorm(from, to)/tau,1.5)*(Math.log(sizeOfGroup)/Math.log(2))));
		/*Run Generate Queries Algorithm 3.5*/
		list=GenerateQueries(sizeOfGroup, tau/36, infNorm, delta_mark);
		/*Query f to find values f(q) for all q in Q*/
		query=Query(from, sizeOfGroup, list, funct);
		/*Run Fixed Queries SFT Algorithm 3.6*/
		retLst=FixedQueries(sizeOfGroup, tau, list, query);
		TimeElements tm=new TimeElements(from, to);
		for (subSet candidate : retLst) {
			Complex coeff=inner_prod(from,sizeOfGroup,funct,(double)candidate.first()/(double)sizeOfGroup,mB);
			if(Complex.Abs(coeff)>=tau){
				tm.add(new Double(candidate.first())/(double)sizeOfGroup, coeff);
			}	
		}
		/*Output L*/
		return tm;
	}
	
	
	/**The function receives the beginning of the segment upon which the SFT algorithm is applied, indicated by from,
	 * sizeOfGroup- the length of the segment, list- which contains the Sets A, B's as indicated in the pseudo-algorithm
	 * 
	 *  The function computes Q*/ 
	 	private static Map<Integer, Complex> Query(int from, int sizeOfGroup, subSet[] list, Function funct) {
	 		Map<Integer, Complex> query=new HashMap<Integer, Complex>();
	 		for (Integer i : list[0]) {
	 			for (int k=1; k<list.length; k++) {
	 				for (Integer j : list[k]) {
	 					int a=(i-j+sizeOfGroup)%sizeOfGroup;
	 					if(!query.containsKey(a))
	 						query.put(a, funct.apply(from+a));
	 				}
	 			}
			}          
		return query;
	}

	/**Algorithm 3.6 FixedQueries*/
	private static List<subSet> FixedQueries(int sizeOfGroup, double tau, subSet[] list, Map<Integer, Complex> query) {
		List<Pair> curr_candidate=new ArrayList<Pair>();
		List<Pair> next_candidate=new ArrayList<Pair>();
		Pair sset2, group=new Pair(0, sizeOfGroup-1);
		int a_tag, b_tag, a, b;
		curr_candidate.add(group);
		for (int l = 1; l < list.length; l++) {
			for (Pair sset : curr_candidate) {
				a_tag=sset.car();
				b_tag=sset.cdr();
				a=a_tag;
				b=(a_tag+b_tag)/2;
				for(int i=0; i<2; i++){
					sset2=new Pair(a,b);
					if(Distinguish(sizeOfGroup, sset2, tau, list[0], list[l], query)==1){
						next_candidate.add(sset2);
					}
					a=b+1;
					b=b_tag;
				}
			}
			curr_candidate=next_candidate;
			next_candidate=new ArrayList<Pair>();
		}
		List<subSet> toRet=new ArrayList<subSet>();
		subSet ss;
		for (Pair pair : curr_candidate) {
			if(pair.car()==pair.cdr()){
				ss=new subSet();
				ss.add_n_keep(pair.car());
				toRet.add(ss);     
			}
		}
		return toRet;
	}
	
	
	/**Algorithm 3.7 Distinguish
	 * The function is used by the SFT algorithm in order to check whether there is a heavy coefficient
	 * in a specific segment -sset
	 * The function returns 1 if there is indeed such a heavy coefficient, and 0 otherwise.
	 */
	private static int Distinguish(int sizeOfGroup, Pair sset2, double tau, subSet A, subSet B, Map<Integer, Complex> query) {
		double est=0;
		int number;
		Complex sum, temp;
		int a=sset2.car();
		int b=sset2.cdr();
		double v = (a+b)/2;
		/*compute est(a,b)*/
		for (Integer i : A) {
			sum = new Complex(0,0);
			for (Integer j : B) {
				Complex chiValue = Complex.Chi(v,j,sizeOfGroup);
				number=(i-j)%sizeOfGroup;
				if(number<0)
					number+=sizeOfGroup;
				temp=Complex.Mult(chiValue,query.get(number));
				sum.Add(temp);
			}
			sum.Div(new Complex(B.size(),0));
			est += Complex.Abs(sum)*Complex.Abs(sum);
					
		}
		est/=(double) A.size();
		
		/*If est(a,b) >= 5/36*tau , decision = 1, else decision = 0*/
		if(tau*5/36<=est)
			return 1;
		return 0;
	}

	/**Algorithm 3.5 GenerateQueries
	 * The function, basically, returns sets of queries to the function, upon which
	 * the algorithm is applied.
	 * GenerateQueries is used in the function SFT. 
	 */
	private static subSet[] GenerateQueries(int sizeOfGroup, double gamma, double infNorm, double delta) {
		int l=0, range, index;
		double size;
		double eta = Math.min(Math.min(gamma, Math.sqrt(gamma)),(gamma/(infNorm)));
		double tmpCoeff = Math.pow(infNorm/eta, 2);
		long mA = (long) ((mA_COEFF) * Math.ceil(tmpCoeff*Math.log(1.0/delta)));
		mB = (long)((mB_COEFF) * Math.ceil(tmpCoeff*Math.log(infNorm/(delta*gamma))));
		mA=Math.max(10, mA);
		mB=Math.max(10, mB);
		index=(int) (Math.ceil(Math.log(sizeOfGroup)/Math.log(2))+1);
		index=Math.max(index, 2);
		subSet[] list=new subSet[index+1];
		list[0]=(createSubgroup(Math.min(mA, sizeOfGroup), sizeOfGroup));
		for (l = 1; l < index; l++) {
			size=Math.min(Math.min(mB, Math.pow(2, l-1)), sizeOfGroup);
			range=(int) Math.min(Math.round(Math.pow(2, l-1)), sizeOfGroup);
			list[l]=(createSubgroup(size, range));
		}
		size=Math.min(mB, sizeOfGroup);
		list[l]=(createSubgroup(size, sizeOfGroup));
		return list;
	}

	/**creates a random subgroup of Zsizeofgroup that has min members.*/
	private static subSet createSubgroup(double min, int sizeOfGroup) {
		Random rand=new Random();
		subSet pair=new subSet();
		min=Math.min(min, sizeOfGroup);
		while(pair.size()<min){
			pair.add_n_keep(rand.nextInt(sizeOfGroup));
		}
		return pair;
	}
	
	/** This function is a probabilistic computation of the inner products of function funct and
	 * a specific character given in candidate.	 
	 * The function is used by the SFT Algorithm.
	 */
	private static Complex inner_prod(int from, int sizeOfGroup, Function funct,
			double key, long numOfElements) {
		Random rand=new Random();
		Complex temp, sum=new Complex();
		for(int i=0;i<numOfElements;i++){
			int r=from+rand.nextInt(sizeOfGroup);
			temp=Complex.Conjecture(Complex.Chi(key,r-from, 1));
			temp=Complex.Mult(funct.apply(r),temp);
			sum.Add(temp);
		}
		sum.Div(new Complex(numOfElements, 0));
		return sum;
	}

}
